package com.seven.leetcode.problems;

import java.util.Arrays;

/**
 * 74. 搜索二维矩阵
 * SearchMatrix
 * https://leetcode-cn.com/problems/search-a-2d-matrix
 * 级别：Easy
 * <p>
 * 编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * <p>
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * <p>
 * 示例:
 * <p>
 * 示例 1：
 * <p>
 * 输入: [[1,3,5,7],[10,11,16,20],[23,30,34,60]] target=3
 * 输出: true
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 *
 * @author : wenguang
 * @date : 2021/3/22 9:26
 */
public class SearchMatrix {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        int target = 3;
        System.out.println("in:\nmatrix->" + Arrays.deepToString(matrix) + "\ntarget: " + target);
        boolean result = searchMatrix(matrix, target);
        System.out.println("out: " + result);
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int l1 = matrix.length;
        for (int i = l1 - 1; i >= 0; i--) {
            int[] tempMatrix = matrix[i];
            int l2 = tempMatrix.length;

            if (l2 > 0) {
                int preIdx = 0;
                int lastIdx = l2 - 1;
                int first = tempMatrix[preIdx];
                int last = tempMatrix[lastIdx];
                if (first == target || last == target) {
                    return true;
                } else if (first > target) {

                } else if (last < target) {
                    return false;
                } else {
                    while (true) {
                        int midIdx = (preIdx + lastIdx) / 2;
                        if (midIdx == preIdx || midIdx == lastIdx) {
                            break;
                        } else if (tempMatrix[midIdx] == target) {
                            return true;
                        } else if (tempMatrix[midIdx] > target) {
                            lastIdx = midIdx;
                        } else if (tempMatrix[midIdx] < target) {
                            preIdx = midIdx;
                        }
                    }
                }
            }
        }

        return false;
    }
}
